package str

func LongestPalindrome2(s string) string {

	if s == "" {
		return s
	}

	var left, right int
	max := 0

	dp := make([][]bool, len(s))

	for i := range dp {
		dp[i] = make([]bool, len(s))
		for j := range dp[i] {
			dp[i][j] = true
		}
	}

	for col := 0; col < len(s); col++ {
		for row := 0; row <= col; row++ {
			if row == col {
				dp[row][col] = true
				continue
			} else {
				if s[row] == s[col] {
					if dp[row+1][col-1] {
						dp[row][col] = true
						if col-row+1 > max {
							left = row
							right = col
							max = col - row + 1
						}
					} else {
						dp[row][col] = false
					}
				} else {
					dp[row][col] = false
				}
			}
		}
	}
	return s[left : right+1]
}

func LongestPalindrome(s string) string {
	start, end := 0, 0

	if s == "" {
		return s
	}

	for i := 0; i < len(s); i++ {
		l1, r1 := expandAroundCenter(s, i, i)
		l2, r2 := expandAroundCenter(s, i, i+1)
		if r1-l1 > end-start {
			start = l1
			end = r1
		}
		if r2-l2 > end-start {
			start = l2
			end = l1
		}
	}
	return s[start : end+1]

}

func expandAroundCenter(s string, left, right int) (int, int) {
	for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 {

	}
	return left + 1, right - 1
}
